package leetcode.editor.cn;
//Java：正则表达式匹配
public class RegularExpressionMatching{
    public static void main(String[] args) {
        Solution solution = new RegularExpressionMatching().new Solution();
        boolean aa = solution.isMatch("aaaa", "aa*");
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isMatch(String s, String p) {
        int sLength = s.length();
        int matchLength = p.length();

        // dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配
        boolean[][] dp = new boolean[sLength + 1][matchLength + 1];
        dp[0][0] = true;

        // 初始化dp数组的第一行
        for (int j = 2; j <= matchLength; j += 2) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= sLength; i++) {
            for (int j = 1; j <= matchLength; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2] || (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
                }
            }
        }
        return dp[sLength][matchLength];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}